#pragma once

using std::cout;
using std::endl;
using std::cin;

namespace xyl {
	/*
		【结点】
	*/
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		list_node(const T& data = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(data)
		{}
	};

	/*
		【迭代器】
	*/
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T, Ref, Ptr> self;

		node* _pNode;

		__list_iterator(node* n = nullptr)
			:_pNode(n)
		{}

		Ref operator*() {
			return _pNode->_data;
		}

		self& operator++() {
			_pNode = _pNode->_next;
			return *this;
		}
		self operator++(int) {
			self tmp = _pNode;
			_pNode = _pNode->_next;
			return tmp;
		}
		self& operator--() {
			_pNode = _pNode->_prev;
			return *this;
		}
		self operator--(int) {
			self tmp = _pNode;
			_pNode = _pNode->_prev;
			return tmp;
		}

		bool operator!=(const self& it) {
			return _pNode != it._pNode;
		}
		bool operator==(const self& it) {
			return _pNode == it._pNode;
		}

		Ptr operator->() {
			return &_pNode->_data; //返回元素的地址
		}
	};

	/*
		【主结构】
	*/
	template<class T>
	class list
	{
	private:
		typedef list_node<T> node;
		
		void buy_head()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

	public:
		//根据传入模板参数不同，实例化出不同的迭代器类
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		// List Constructor
		list() //empty container
		{
			/*_head = new node;
			_head->_next = _head;
			_head->_prev = _head;*/
			buy_head();
		}

		list(size_t n, const T& val = T()) //Constructs a container with n elements. Each element is a copy of val.
		{
			buy_head();
			while (n--) {
				push_back(val);
			}
		}
		list(int n, const T& val = T()) //Constructs a container with n elements. Each element is a copy of val.
		{
			buy_head();
			while (n--) {
				push_back(val);
			}
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last) //Constructs a container with as many elements as the range [first,last)
		{
			buy_head();
			while (first != last) {
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& ls) //Construct a deep-copy of ls
		{
			//buy_head();
			//for (auto ele : ls) {
			//	push_back(ele);
			//}

			buy_head();
			list<T> tmp(ls.begin(), ls.end()); //现代写法——窃取劳动成果
			swap(tmp);
		}

		list<T>& operator=(list<T> ls) //Deep-Assign ls to *this (clear all previous contents in *this)
		{
			////判断this的size和ls的size
			////1. this的大，就把ls赋值给this，并delete掉this后面的
			////2. ls的大，就把ls赋值给this，不够的部分再push_back

			//if (this != &ls) //防止自己赋值给自己
			//{
			//	iterator it = begin();
			//	if (size() > ls.size()) { // 1.
			//		const_iterator ls_it = ls.begin();
			//		while (ls_it != ls.end()) {
			//			*it = *ls_it;
			//			++ls_it;
			//			++it;
			//		}
			//		while (it != end()) {
			//			it = erase(it);
			//		}
			//	}
			//	else { // 2.
			//		const_iterator ls_it = ls.begin();
			//		while (it != end()) {
			//			*it = *ls_it;
			//			++ls_it;
			//			++it;
			//		}
			//		while (ls_it != ls.end()) {
			//			push_back(*ls_it);
			//			++ls_it;
			//		}
			//	}
			//}
			//return *this;

			//现代写法——窃取劳动成果
			swap(ls);
			return *this;
		}

		// List Destructor
		~list() {
			clear();
			delete _head;
		}

		// List Capacity
		bool empty() const {
			return _head->_next == _head;
		}

		size_t size() const {
			node* tmp = _head->_next;
			size_t count = 0;
			while (tmp != _head) {
				++count;
				tmp = tmp->_next;
			}
			return count;
		}

		// List Access
		T& front() {
			return *begin();
		}
		const T& front() const {
			return *begin();
		}
		T& back() {
			return *(--end());
		}
		const T& back() const {
			return *(--end());
		}

		// List Iterator
		iterator begin() {
			return iterator(_head->_next);
		}

		const_iterator begin() const {
			return const_iterator(_head->_next);
		}

		iterator end() {
			return iterator(_head);
		}

		const_iterator end() const {
			return const_iterator(_head);
		}

		// List Modify 
		void push_back(const T& val)
		{
			/*node* new_node = new node(val);
			node* tail = _head->_prev;
			tail->_next = new_node;
			new_node->_prev = tail;
			new_node->_next = _head;
			_head->_prev = new_node;*/
			insert(--begin(), val);
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		void pop_back()
		{
			/*node* new_tail = _head->_prev->_prev;
			delete _head->_prev;
			new_tail->_next = _head;
			_head->_prev = new_tail;*/

			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}

		iterator erase(iterator pos)
		{
			node* next = pos._pNode->_next;
			node* prev = pos._pNode->_prev;
			delete pos._pNode;
			next->_prev = prev;
			prev->_next = next;

			return next;
		}

		iterator insert(iterator pos, const T& val)
		{
			node* new_node = new node(val);
			node* prev = pos._pNode->_prev;
			prev->_next = new_node;
			new_node->_prev = prev;
			new_node->_next = pos._pNode;
			pos._pNode->_prev = new_node;

			return pos._pNode;
		}

		void clear() {
			while (!empty()) {
				pop_back();
			}
		}

		void swap(list<T>& ls) {
			std::swap(_head, ls._head); //只需要交换_head指针
		}

	private:
		// List Member Value
		node* _head;
	};


	///////////////////////////////////////end of class, below are tests.

	void printList(const list<int>& ls) {
		for (auto e : ls) {
			cout << e << ' ';
		}
		cout << endl;
	}

	void test_1() {
		// constructors used in the same order as described above:
	  list<int> first;                                // empty list of ints
	  list<int> second (4,100);                       // four ints with value 100
	  list<int> third (second.begin(),second.end());  // iterating through second
	  list<int> fourth (third);                       // a copy of third

	  // the iterator constructor can also be used to construct from arrays:
	  int myints[] = {16,2,77,29};
	  list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

	  cout << "The contents of fifth are: ";
	  for (list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
		cout << *it << ' ';

	  cout << '\n';
	}

	void test_2() {
		list<int> first(3);      // list of 3 zero-initialized ints
		list<int> second(5);     // list of 5 zero-initialized ints

		second = first;
		first = list<int>();

		cout << "Size of first: " << int(first.size()) << '\n';
		cout << "Size of second: " << int(second.size()) << '\n';
	}

	void test_3() {
		int myints[] = { 75,23,65,42,13 };
		list<int> mylist(myints, myints + 5);

		cout << "mylist contains:";
		for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;

		cout << '\n';
	}

	void test_4() {
		int myints[] = { 75,23,65,42,13 };
		list<int> mylist(myints, myints + 5);

		cout << "mylist contains:";
		for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;

		cout << '\n';
	}

	void test_5() {
		list<int> mylist;
		int sum(0);

		for (int i = 1; i <= 10; ++i) mylist.push_back(i);

		while (!mylist.empty())
		{
			sum += mylist.front();
			mylist.pop_front();
		}

		cout << "total: " << sum << '\n';
	}

	void test_6() {
		list<int> myints;
		cout << "0. size: " << myints.size() << '\n';

		for (int i = 0; i < 10; i++) myints.push_back(i);
		cout << "1. size: " << myints.size() << '\n';

		//myints.insert(myints.begin(), 10, 100);
		//cout << "2. size: " << myints.size() << '\n';

		myints.pop_back();
		cout << "3. size: " << myints.size() << '\n';
	}

	void test_7() {
		list<int> mylist;

		mylist.push_back(77);
		mylist.push_back(22);

		// now front equals 77, and back 22

		mylist.front() -= mylist.back();

		cout << "mylist.front() is now " << mylist.front() << '\n';
	}

	void test_8() {
		list<int> mylist;

		mylist.push_back(10);

		while (mylist.back() != 0)
		{
			mylist.push_back(mylist.back() - 1);
		}

		cout << "mylist contains:";
		for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;

		cout << '\n';
	}

	void test_9() {
		list<int> mylist(2, 100);         // two ints with a value of 100
		mylist.push_front(200);
		mylist.push_front(300);

		cout << "mylist contains:";
		for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;

		cout << '\n';
	}

	void test_10() {
		list<int> mylist;
		mylist.push_back(100);
		mylist.push_back(200);
		mylist.push_back(300);

		cout << "Popping out the elements in mylist:";
		while (!mylist.empty())
		{
			cout << ' ' << mylist.front();
			mylist.pop_front();
		}

		cout << "\nFinal size of mylist is " << mylist.size() << '\n';
	}

	void test_11() {
		list<int> mylist;
		int myint;

		cout << "Please enter some integers (enter 0 to end):\n";

		do {
			cin >> myint;
			mylist.push_back(myint);
		} while (myint);

		cout << "mylist stores " << mylist.size() << " numbers.\n";
	}

	void test_12() {
		list<int> mylist;
		int sum(0);
		mylist.push_back(100);
		mylist.push_back(200);
		mylist.push_back(300);

		while (!mylist.empty())
		{
			sum += mylist.back();
			mylist.pop_back();
		}

		cout << "The elements of mylist summed " << sum << '\n';
	}

	void test_13() {
		list<int> mylist;
		list<int>::iterator it;

		// set some initial values:
		for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5

		it = mylist.begin();
		++it;       // it points now to number 2           ^

		mylist.insert(it, 10);                        // 1 10 2 3 4 5

		
		for (it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;
		cout << '\n';
	}

	void test_14() {
		list<int> mylist;
		list<int>::iterator it1;

		// set some values:
		for (int i = 1; i < 10; ++i) mylist.push_back(i * 10);

		// 10 20 30 40 50 60 70 80 90
		it1 = mylist.begin();
		++it1;
		++it1;
		mylist.erase(it1);

		cout << "mylist contains:";
		for (it1 = mylist.begin(); it1 != mylist.end(); ++it1)
			cout << ' ' << *it1;
		cout << '\n';
	}

	void test_15() {
		list<int> mylist;
		list<int>::iterator it;

		mylist.push_back(100);
		mylist.push_back(200);
		mylist.push_back(300);

		cout << "mylist contains:";
		for (it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;
		cout << '\n';

		mylist.clear();
		mylist.push_back(1101);
		mylist.push_back(2202);

		cout << "mylist contains:";
		for (it = mylist.begin(); it != mylist.end(); ++it)
			cout << ' ' << *it;
		cout << '\n';
	}

	void test_16() {
		list<int> first(3, 100);   // three ints with a value of 100
		list<int> second(5, 200);  // five ints with a value of 200

		first.swap(second);

		cout << "first contains:";
		for (list<int>::iterator it = first.begin(); it != first.end(); it++)
			cout << ' ' << *it;
		cout << '\n';

		cout << "second contains:";
		for (list<int>::iterator it = second.begin(); it != second.end(); it++)
			cout << ' ' << *it;
		cout << '\n';
	}
}